package com.example.design.leetcode.dynamic;

//剑指 Offer 10 - II. 青蛙跳台阶问题
//    一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。
//
//    答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
//
//    示例 1：
//    输入：n = 2
//    输出：2
//
//    示例 2：
//    输入：n = 7
//    输出：21
//
//    示例 3：
//    输入：n = 0
//    输出：1
//    提示：
//
//    0 <= n <= 100
//    注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/

public class Practice42 {

    // 状态定义： F[n] 表示的含义为斐波那契数列中第 n 个数字
    public static int numWays(int n) {
        // 初始状态： F[0] = 1, F[1] = 1，因为在计算 n 时需要 2 个元素，所以要初始化 2 个值；
        int n0 = 1;
        int n1 = 1;
        int sum;
        for (int i = 0; i < n; i++) {
            // 转移方程：F(n)=F(n−1)+F(n−2)
            sum = (n0 + n1)%1000000007;
            // 两个指针后移
            n0 = n1;
            n1 = sum;
        }

        return n0;
    }

    public static void main(String[] args) {
        System.out.println(numWays2(4));
    }

    // 状态定义： F[n] 表示的含义为斐波那契数列中第 n 个数字
    public static int numWays2(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        // 状态定义
        int[] temp = new int[n];
        // 边界条件
        temp[0] = 1;
        temp[1] = 2;

        for (int i = 2; i < n; i++) {
            // 状态定义方程
            temp[i] = temp[i-1] + temp[i-2];
        }
        return temp[n - 1];
    }
}
